package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 面试题 16.19. 水域大小
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/1 13:15
 */
public class PondSizes {

    private int sum;

    public int[] pondSizes(int[][] land) {
        List<Integer> res = new ArrayList<>();
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                sum = 0;
                if (land[i][j] == 0) {
                    find(land, i, j, dirs);
                    res.add(sum);
                }
            }
        }
        return res.stream().mapToInt(Integer::valueOf).sorted().toArray();
    }

    public void find(int[][] land, int i, int j, int[][] dirs) {
        sum++;
        land[i][j] = -1;
        for (int[] dir : dirs) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            if (newI < 0 || newI >= land.length || newJ < 0 || newJ >= land[0].length || land[newI][newJ] != 0) {
                continue;
            }
            find(land, newI, newJ, dirs);
        }
    }


}
